
/*
 * 描述

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 
0
≤
n
≤
1000
0≤n≤1000
要求：空间复杂度 
O
(
1
)
O(1) ，时间复杂度 
O
(
n
)
O(n) 。

如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
以上转换过程如下图所示：
 */
public class 反转链表 {
    
    public static void main(String[] args) {
        
        ListNode node = new ListNode(1);
        node.next = new ListNode(2);
        node.next.next = new ListNode(3);
        node.next.next.next = new ListNode(4);
        node.next.next.next.next = new ListNode(5);
        node.next.next.next.next.next = new ListNode(6);

        ListNode pre = reverseList(node);

        System.out.println(pre.toString());
        

    }

    private static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr!= null) {
            ListNode nextNode = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextNode;
        }
        return prev;
    }

    private static class ListNode{

        public int val;
        public ListNode next;

        public ListNode(int val){

            this.val = val;
        }

        public String toString(){

            StringBuilder builder = new StringBuilder();

            builder.append(val);
            builder.append(",");

            ListNode nextNode = next;

            while(null!=nextNode){

                builder.append(nextNode.val);
                builder.append(",");
                nextNode = nextNode.next;
            }
            

            return builder.toString();
        }

    }
}
